package io.gimo.study.design_pattern.factory.abstract_factory.product;


import io.gimo.study.design_pattern.factory.abstract_factory.Sortor;

import java.util.Arrays;

public class BinaryInsertionSortor implements Sortor {

	@Override
	public void sort(int[] target) {
		for (int i = 0; i < target.length; i++) {
			// 记录中间值
			int temp = target[i];
			// 左端点位置
			int min_pos = 0;
			// 右端点位置
			int max_pos = i - 1;
			// 中间位置
			int mid_pos = 0;
			
			while(min_pos <= max_pos){
				mid_pos = (min_pos + max_pos)/2;
				if(target[i] < target[mid_pos])
					max_pos = mid_pos -1;
				else
					min_pos = mid_pos + 1;
			}
			for (int j = i - 1; j >= min_pos; j--) 
				target[j+1] = target[j];
			if(min_pos != i)
				target[min_pos] = temp ;
			
		}
		System.out.println(Arrays.toString(target));
	}

}
